#include <iostream>

// 1545. 找出第 N 个二进制字符串中的第 K 位
// 给你两个正整数 n 和 k，二进制字符串  Sn 的形成规则如下：
//S1 = "0"
//当 i > 1 时，Si = Si-1 + "1" + reverse(invert(Si-1))
//其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）。

class Solution {
public:
    char findKthBit(int n, int k) {
        if(k == 1) return '0';
        int mid = 1 << (n-1);   // 中间位置 2^(n-1)
        if(k == mid) return '1';
        else if(k < mid) return findKthBit(n-1,k);  // 前半部分找
        else {
            // 后半部分找
            k = mid * 2 - k;
            return invert(findKthBit(n-1,k));
        }
    }

private:
    char invert(char bit) {
        return (char)('0' + '1' - bit);
    }
};
int main() {
    std::cout << Solution().findKthBit(3,1) << std::endl;   // 0
    std::cout << Solution().findKthBit(4,11) << std::endl;  // 1
    std::cout << Solution().findKthBit(1,1) << std::endl;  // 0
    std::cout << Solution().findKthBit(2,3) << std::endl;  // 1


    return 0;
}
